/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: JZ39 数组中出现次数超过一半的数字
 * <a href="https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11181&ru=/exam/oj">...</a>
 * User: DELL
 * Date: 2023-05-18
 * Time: 13:14
 */
public class Solution {

    /**
     * 本题就是经典的互相消耗的方法,因为候选数字出现的次数大于原数组中数字的一半,
     * 因此如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非
     * 众数，那么如果存在众数，最后留下的数肯定是众数
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int num = array[0];
        int count = 1;
        for (int i = 1; i < array.length; i++) {
            if (count == 0) {
                num = array[i];
                count++;
            } else {
                if (num == array[i]) {
                    count++;
                } else {
                    count--;
                }
            }
        }
        return num;
    }
}